아커만 함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 정의와 특성
4. 값들의 표
5. 아커만 함수가 원시 재귀 함수가 아니라는 증명
6. 역함수
7. 벤치마크로 사용
8. 계산
9. Properties
참조

1. 개요

아커만 함수는 1920년대에 가브리엘 수단과 빌헬름 아커만에 의해 발견된, 계산 가능 함수 중 하나이다. 2변수 함수 형태로 정의되며, 덧셈, 곱셈, 거듭제곱 연산을 일반화하는 방식으로 표현된다. 아커만 함수는 재귀적으로 정의되며, m과 n의 값이 커짐에 따라 매우 빠르게 증가하는 특징을 가진다. 이 함수는 덧셈과 1을 빼는 연산만으로 정의되지만, 재귀의 깊이가 매우 깊어 지수 함수, 팩토리얼 함수 등 다른 원시 재귀 함수보다 빠르게 증가한다. 아커만 함수는 컴파일러의 재귀 최적화 능력을 평가하는 벤치마크로 사용되며, 한국의 컴퓨터 과학 분야에서도 계산 복잡도 이론과 알고리즘 분석의 중요한 예시로 활용된다.

더 읽어볼만한 페이지

계산 가능성 이론 - 처치-튜링 논제
처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
계산 가능성 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
조합론 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.
조합론 - 계승 (수학)
계승은 음이 아닌 정수 n에 대해 1부터 n까지의 자연수를 곱한 값으로, 0의 계승은 1로 정의되며, 대칭군의 크기와 같다는 성질을 통해 기수로 확장될 수 있고, 다중 계승, 지수 계승 등으로 확장 및 응용되어 다양한 분야에서 활용된다.
특수 함수 - 람베르트 W 함수
람베르트 W 함수는 we^w = z를 만족하는 w를 찾는 람베르트 이름을 딴 역함수 관계를 가지며, 여러 분야에서 지수 함수 방정식을 푸는 데 응용되는 무한히 많은 가지를 가진 함수이다.
특수 함수 - 감마 함수
감마 함수는 양의 실수부를 갖는 복소수 z에 대해 오일러 적분으로 정의되고 해석적 연속을 통해 복소평면 전체로 확장된 팩토리얼 함수의 일반화로서, 수학, 물리학, 공학 등 다양한 분야에서 활용되며 여러 표현과 성질을 가진다.

아커만 함수
함수 정보
이름	아커만 함수
로마자 표기	Akeoman Ham-su
분야	계산 가능성 이론, 수학
정의
유형	재귀 함수
창시자	빌헬름 아커만
창시 시기	1928년
특징	모든 재귀 함수를 계산할 수 있는 튜링 완전성을 가짐 계산 복잡도가 매우 빠르게 증가함
형식 정의
함수 정의	A(m, n) = n + 1 (if m = 0) A(m, n) = A(m - 1, 1) (if m > 0 and n = 0) A(m, n) = A(m - 1, A(m, n - 1)) (if m > 0 and n > 0)
변수	m: 음이 아닌 정수 n: 음이 아닌 정수
값의 증가
증가 속도	매우 빠름 (지수 함수보다 훨씬 빠르게 증가)
활용
활용 분야	컴퓨터 과학: 알고리즘의 성능 분석, 재귀 호출의 깊이 측정 수학: 계산 가능성 이론, 집합론
특징
계산 복잡도	계산 복잡도가 높아 큰 수에 대해서는 계산이 매우 어려움
역함수	아커만 함수의 역함수는 매우 느리게 증가함
기타
관련 함수	페테르 함수

2. 역사

1920년대 후반, 다비트 힐베르트(David Hilbert)의 제자였던 수학자 가브리엘 수단(Gabriel Sudan)과 빌헬름 아커만(Wilhelm Ackermann)은 계산의 기초를 연구하고 있었다.^[19] 당시 힐베르트는 모든 계산 가능 함수가 원시 재귀 함수일 것이라고 추측했으나^[12], 수단과 아커만의 연구는 이와 다른 결과를 보여주었다. 두 사람은 원시 재귀 함수가 아니면서도 완전히 정의된 계산 가능 함수를 발견한 것으로 인정받는다.^[19]^[11]

1927년 수단은 먼저 수단 함수를 발표했다. 그 직후인 1928년, 아커만은 독자적으로 3개의 변수를 사용하는 함수 $\varphi(m, n, p)$ 를 발표했다.^[10] 이 함수는 변수 ''p''의 값에 따라 기본적인 산술 연산을 확장하는 방식으로 정의된다.

: $\varphi(m, n, 0) = m+n$ (덧셈)

: $\varphi(m, n, 1) = m\cdot n$ (곱셈)

: $\varphi(m, n, 2) = m^n$ (거듭제곱)

그리고 ''p''가 2보다 클 경우, 이 기본 연산들을 하이퍼 연산과 유사한 방식으로 확장한다.

힐베르트는 자신의 저서 Über das Unendliche|위버 다스 우넨틀리헤^de^[12]에서 아커만 함수가 원시 재귀 함수가 아닐 것이라고 가설을 세웠다. 이 가설은 아커만 자신에 의해 증명되었으며, 그의 논문 Zum Hilbertschen Aufbau der reellen Zahlen|춤 힐베르트셴 아우프바우 데어 레알렌 찰렌^de^[10]^[13]에 실렸다.^[17]^[20]

이후 1935년 로저 페테르(Rózsa Péter)^[14]와 라파엘 로빈슨(Raphael Robinson)은 아커만 함수의 2변수 버전을 개발했으며, 이 형태가 현재 많은 문헌에서 선호되고 있다.^[21] 아커만 함수의 다른 여러 버전들도 연구되었다.^[2]

3. 정의와 특성

1920년대 후반, 다비트 힐베르트의 제자였던 수학자 가브리엘 수단과 빌헬름 아커만은 계산 이론의 기초를 연구하며 원시 재귀 함수가 아닌 계산 가능 함수를 발견하는 중요한 기여를 했다.^[19]^[11] 수단은 수단 함수를 발표했고, 1928년 아커만은 독자적으로 3개의 변수를 사용하는 함수 $\varphi(m, n, p)$ 를 발표했다.^[10] 이 함수는 ''p'' 값에 따라 덧셈 ( $p=0$ ), 곱셈 ( $p=1$ ), 거듭제곱 ( $p=2$ ) 등 기본적인 산술 연산을 나타내며, ''p''가 3 이상으로 커지면 하이퍼 연산으로 확장된다.

힐베르트는 아커만 함수가 원시 재귀 함수가 아닐 것이라고 추측했으며, 아커만 자신이 이를 증명하여 발표했다.^[17]^[20]^[13]

이후 로저 페테르와 라파엘 로빈슨은 오늘날 가장 널리 알려진 2변수 형태의 아커만 함수 $A(m, n)$ 를 정의했다.^[21]^[14] 이 함수는 음이 아닌 정수 ''m''과 ''n''에 대해 다음과 같이 재귀적으로 정의된다.

: $A(m, n) =\begin{cases}n+1 & \mbox{만약 } m = 0 \\A(m-1, 1) & \mbox{만약 } m > 0, n = 0 \\A(m-1, A(m, n-1)) & \mbox{만약 } m > 0, n > 0.\end{cases}$

이 정의만 보면 함수 계산이 항상 종료되는지 명확하지 않을 수 있다. 하지만 재귀 호출이 일어날 때마다 첫 번째 인자 ''m''이 줄어들거나, ''m''은 그대로 유지되면서 두 번째 인자 ''n''이 줄어든다. 이는 인자의 쌍 (''m'', ''n'')이 사전식 순서에 따라 항상 감소함을 의미하므로, 계산은 유한한 단계 안에서 반드시 끝난다. 그러나 ''m''이 줄어들 때 ''n''이 매우 크게 증가할 수 있어 계산 과정이 길어지고 결과값이 커질 수 있다.

아커만 함수는 다른 수학적 표기법으로도 표현될 수 있다.

커누스 윗화살표 표기법: $A(m,n)=2\uparrow^{m-2} (n+3) - 3$ (단, $m \ge 2$ )
콘웨이 연쇄 화살표 표기법: $A(m,n)=(2\rightarrow(n+3)\rightarrow(m-2))-3$ (단, $m \ge 2$ )

''m''의 값이 작을 때 아커만 함수는 상대적으로 천천히 증가하며, 기본적인 산술 연산과 관련된다.

$A(0, n) = n+1$ (덧셈)
$A(1, n) = n+2$ (덧셈)
$A(2, n) = 2n+3$ (곱셈과 유사한 선형 증가)
$A(3, n) = 2^{n+3} - 3$ (거듭제곱, 지수적 증가)

하지만 ''m''이 4 이상이 되면 함수의 값은 상상하기 어려울 정도로 폭발적으로 증가한다. 예를 들어,

A(4, 2)

는

2^{65536} - 3

으로, 이 값은 십진수로 약 19,729자리의 매우 큰 수이다.^[6]

A(4, 3)

의 값은

A(3, A(4, 2)) = 2^{A(4, 2)+3} - 3 = 2^{2^{65536}} - 3

으로, 그 크기는 일반적인 표기법으로는 나타내기조차 어렵다.

아커만 함수의 흥미로운 특징 중 하나는 오직 '1 더하기'와 '1 빼기' 연산만으로 정의된다는 점이다. 함수의 엄청난 증가 속도는 복잡한 연산이 아닌, 깊게 중첩된 재귀 구조 자체에서 비롯된다. 이는 아커만 함수의 계산 시간이 결과값 이상으로 매우 길어질 수 있음을 의미하기도 한다.

결정적으로 아커만 함수는 원시 재귀 함수가 아니다. 모든 원시 재귀 함수는 이론적으로 계산 가능하지만, 아커만 함수(특히

f(n) = A(n, n)

과 같이 인자를 하나로 만든 변형 함수)는 지수 함수나 팩토리얼 함수를 포함한 어떤 원시 재귀 함수보다도 훨씬 빠르게 증가한다. 이러한 특성 때문에 아커만 함수는 계산 가능성 이론에서 계산 가능하지만 원시 재귀적이지 않은 함수의 대표적인 예시로 사용된다. 아커만 함수의 증가 속도는 빠르게 증가하는 계급의

f_{\omega}(n)

과 비슷한 수준으로 알려져 있다.

간단한 계산 예시로

A(1, 2)

를 보면 다음과 같이 계산된다.

:

\begin{align}A(1,2) &= A(0, A(1, 1)) \\&= A(0, A(0, A(1, 0))) \quad (\because A(1, 1) = A(0, A(1, 0))) \\&= A(0, A(0, A(0, 1))) \quad (\because A(1, 0) = A(0, 1)) \\&= A(0, A(0, 2)) \quad (\because A(0, 1) = 1+1 = 2) \\&= A(0, 3) \quad (\because A(0, 2) = 2+1 = 3) \\&= 4 \quad (\because A(0, 3) = 3+1 = 4)\end{align}

4. 값들의 표

아커만 함수를 계산한 값은 무한한 표로 나타낼 수 있다. 표의 값을 결정하는 규칙은 다음과 같다. 표의 가장 윗 행에는 자연수를 순서대로 놓고, 특정 칸의 값을 구하려면 바로 왼쪽 칸의 값을 먼저 확인한다. 그 다음, 바로 위 행에서 방금 확인한 왼쪽 칸의 값에 해당하는 열의 값을 찾는다. 만약 가장 왼쪽 열(''n''=0)이라 왼쪽에 수가 없다면, 단순히 바로 위 행의 ''n''=1이었던 값, 즉 A(''m''-1, 1)의 값을 가져온다. 다음은 아커만 함수 값의 표 일부이다.

''A''(''m'', ''n'')의 값
m＼n	0	1	2	3	4	n
0	1	2	3	4	5	$n + 1$
1	2	3	4	5	6	$n + 2 = 2 + (n + 3) - 3$
2	3	5	7	9	11	$2n + 3 = 2 \times (n + 3) - 3$
3	5	13	29	61	125	$2^{n+3} - 3$
4	13	65533	$2^{65536} - 3$	$2^{2^{65536}} - 3$	$2^{2^{2^{65536}}} - 3$	$\begin{matrix}\underbrace}} - 3 \\ n+3 \text{ 개의 2}\end{matrix}$
5	65533	$\begin{matrix}\underbrace}} - 3 \\ 65536 \text{ 개의 2}\end{matrix}$	$A(4, A(5, 1))$	$A(4, A(5, 2))$	$A(4, A(5, 3))$	$A(4, A(5, n-1))$

표에서 볼 수 있듯이 ''m''과 ''n''이 조금만 커져도 그 값은 매우 빠르게 증가한다. 예를 들어 $A(4, 2)$ 의 값은 $2^{65536} - 3$ 인데, 이는 $2$ 를 65,536번 거듭제곱한 후 3을 뺀 값으로, 일반적인 십진법으로 표기하기에는 너무 크다. 이러한 큰 수를 표현하기 위해 커누스 윗화살표 표기법이나 하이퍼 연산 등이 사용된다.

표의 값들을 함수 정의와 관련된 재귀적 표현으로 나타내면 패턴을 더 명확하게 볼 수 있다.

''A''(''m'', ''n'')의 값 (재귀적 표현)
m＼n	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	$n + 1$
1	A(0, 1)	A(0, A(1, 0))	A(0, A(1, 1))	A(0, A(1, 2))	A(0, A(1, 3))	A(0, A(1, n-1))
2	A(1, 1)	A(1, A(2, 0))	A(1, A(2, 1))	A(1, A(2, 2))	A(1, A(2, 3))	A(1, A(2, n-1))
3	A(2, 1)	A(2, A(3, 0))	A(2, A(3, 1))	A(2, A(3, 2))	A(2, A(3, 3))	A(2, A(3, n-1))
4	A(3, 1)	A(3, A(4, 0))	A(3, A(4, 1))	A(3, A(4, 2))	A(3, A(4, 3))	A(3, A(4, n-1))
5	A(4, 1)	A(4, A(5, 0))	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))	A(4, A(5, n-1))

아커만 함수 값은 매우 크지만, 커누스 윗화살표 표기법, 콘웨이 연쇄 표기법, 하이퍼 연산 등을 사용하면 다음과 같이 간결하게 나타낼 수 있다 ( $m \ge 3$ 인 경우).^[6]

$A(m, n) = (2 \uparrow^{m-2} (n+3)) - 3$
$A(m, n) = (2 \rightarrow (n+3) \rightarrow (m-2)) - 3$
$A(m, n) = \operatorname{hyper}(2, m, n+3) - 3 = \operatorname{hyper}_m(2, n+3) - 3$

여기서

\uparrow

는 커누스 윗화살표 표기법,

\rightarrow

는 콘웨이 연쇄 화살표 표기법,

\operatorname{hyper}

는 하이퍼 연산을 나타낸다.

아커만 함수는 매우 빠르게 증가하지만, 그레이엄 수와 같이 훨씬 더 빠르게 증가하여 작은 개수의 커누스 윗화살표로도 표현하기 어려운 큰 수도 존재한다.

충분히 큰 ''x''에 대해, 아커만 함수의 값은 급증 함수

f_{\omega}

를 사용하여

A(x, a) \approx f_{\omega}(x)

(

a

는 상수)와 같이 근사할 수 있다.

5. 아커만 함수가 원시 재귀 함수가 아니라는 증명

아커만 함수는 어떤 원시 재귀 함수보다도 빠르게 증가하기 때문에, 그 자체는 원시 재귀 함수가 아니다.

핵심 증명 아이디어는 모든 원시 재귀 함수 $f(x_1,\ldots,x_n)$ 에 대해, 모든 음이 아닌 정수 $x_1,\ldots,x_n$ 에서 다음 부등식을 만족하는 음이 아닌 정수 $t$ 가 존재함을 보이는 것이다.^[22]

: $f(x_1,\ldots,x_n)$

여기서 $A$ 는 아커만 함수이고, $\mathrm{max}_i x_i$ 는 입력값 $x_1,\ldots,x_n$ 중 가장 큰 값이다.

만약 이 명제가 참이라면, 아커만 함수 $A$ 는 원시 재귀 함수가 될 수 없다. $A$ 가 원시 재귀 함수라고 가정하면, 위 명제에 따라 어떤 $t$ 가 존재하여 모든 $x$ 에 대해 $A(x,x) < A(t, \max(x,x)) = A(t, x)$ 가 성립해야 한다. 그러나 $x=t$ 를 대입하면 $A(t,t) < A(t,t)$ 라는 모순이 발생한다.

이 명제를 증명하기 위해, 아커만 함수보다 느리게 증가하는 모든 함수들의 집합 $\mathcal{A}$ 를 다음과 같이 정의한다.

: $\mathcal{A}=\left\{ f \mid \exists t\ \forall x_1\cdots \forall x_n:\ f(x_1,\ldots,x_n)$

그리고 이 집합 $\mathcal{A}$ 가 모든 원시 재귀 함수를 포함함을 보인다. 이는 집합 $\mathcal{A}$ 가 원시 재귀 함수의 기본 구성 요소인 상수 함수, 다음수 함수, 투영 함수를 포함하고, 함수 합성과 원시 재귀 연산에 대해 닫혀 있음을 증명함으로써 달성된다.^[22]

다비트 힐베르트는 그의 저서 ''Über das Unendliche''^[12]에서 아커만 함수가 원시 재귀적이지 않다고 추측했다. 이 추측은 힐베르트의 제자였던 빌헬름 아커만에 의해 1928년에 증명되었고, 그의 논문에 발표되었다.^[10]^[13]

6. 역함수

함수 $f(n) = A(n, n)$ 는 매우 빠르게 증가하므로, 그 역함수 $f^{-1}$ 는 매우 느리게 증가한다. 이 '''역 아커만 함수''' $f^{-1}$ 는 일반적으로 ''' $\alpha$ '''로 표기한다. 실제로 $A(4, 4)$ 는 $2^{2^{2^{2^{16}}}}$ 정도의 매우 큰 수이므로, 모든 실제적인 입력 크기 ''n''에 대해 $\alpha(n)$ 은 5보다 작다.

이 역함수는 분리 집합 자료 구조나 최소 신장 트리에 대한 베르나르 샤젤의 알고리즘과 같은 일부 알고리즘의 시간 복잡도 분석에 나타난다. 로버트 타잔은 1975년 논문에서 분리 집합 자료 구조의 탐색 및 결합 연산의 시간 복잡도가 $O(\alpha(n))$ 임을 보였다.^[15] 때때로 아커만의 원래 함수나 다른 변형 함수가 사용되기도 하지만, 모두 비슷한 비율로 빠르게 증가한다. 특히 어떤 수정된 함수는 식에서 ''−3''과 같은 항을 제거하여 단순화하기도 한다.

역 아커만 함수의 2변수 변형은 다음과 같이 정의할 수 있다. 여기서 $\lfloor x \rfloor$ 는 바닥 함수이다:

: $\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.$

이 함수는 위에서 언급한 알고리즘들을 더 정확하게 분석하여 더 정교한 시간 복잡도 상한을 얻는 데 사용된다. 분리 집합 자료 구조에서 ''m''은 연산의 수를 나타내고 ''n''은 원소의 수를 나타낸다. 최소 신장 트리 알고리즘에서 ''m''은 간선의 수를 나타내고 ''n''은 정점의 수를 나타낸다. $\alpha(m, n)$ 에 대한 약간 다른 정의들도 존재하는데, 예를 들어 $\log_2 n$ 이 ''n''으로 대체되거나 바닥 함수가 천장 함수로 바뀌는 경우 등이다.

다른 연구에서는 ''m''을 상수로 고정하여 특정 행에 대한 역함수를 정의하기도 한다.^[23]

역 아커만 함수는 원시 재귀 함수이다. 자연수 ''n''에 대해 $A(m-1,m-1) 을 만족하는 ''m''을 찾아 \alpha(n)=m 으로 정의하기도 한다. 이 정의에 따르면 역 아커만 함수는 모든 자연수에 대해 정의되고 상한은 없지만, 매우 느리게 증가한다.$

7. 벤치마크로 사용

아커만 함수는 그 정의상 극한으로 깊은 재귀라는 특징 때문에 컴파일러가 재귀 호출을 얼마나 잘 최적화하는지 평가하는 벤치마크로 사용될 수 있다. 아커만 함수를 이러한 방식으로 사용한 최초의 사례는 1970년 드라고슈 바이다(Dragoș Vaida)에 의해 발표되었으며, 거의 동시에 1971년 윙베 순드블라드(Yngve Sundblad)에 의해서도 사용되었다.^[24]

순드블라드의 연구는 이후 헤트스톤 벤치마크의 공동 저자인 브라이언 위치만(Brian Wichmann)에 의해 1975년과 1982년 사이에 발표된 세 편의 논문에서 활용되었다.^[25]^[26]^[27]

8. 계산

아커만 함수의 재귀적 정의는 자연스럽게 항 재작성 시스템(TRS)으로 변환될 수 있다.

=== 2항 아커만 함수 ===

2항 아커만 함수 $\operatorname{A}(m, n)$ 의 정의는 다음과 같은 축약 규칙을 따른다.

: $\begin{array}{lll}\text{(r1)} & A(0,n) & \rightarrow & S(n) \\\text{(r2)} & A(S(m),0) & \rightarrow & A(m,S(0)) \\\text{(r3)} & A(S(m),S(n)) & \rightarrow & A(m,A(S(m),n))\end{array}$

여기서 $S(n)$ 은 $n+1$ 을 의미한다.

'''예시: $A(1,2) \rightarrow_{*} 4$ 계산'''

축약 시퀀스는 다음과 같다.^[4]

가장 왼쪽-바깥쪽(1단계) 전략	가장 왼쪽-안쪽(1단계) 전략
$A(S(0),S(S(0)))$	$A(S(0),S(S(0)))$
$\rightarrow_{r3} A(0,A(S(0),S(0)))$	$\rightarrow_{r3} A(0,A(S(0),S(0)))$
$\rightarrow_{r1} S(A(S(0),S(0)))$	$\rightarrow_{r3} A(0,A(0,A(S(0),0)))$
$\rightarrow_{r3} S(A(0,A(S0,0)))$	$\rightarrow_{r2} A(0,A(0,A(0,S(0))))$
$\rightarrow_{r1} S(S(A(S(0),0)))$	$\rightarrow_{r1} A(0,A(0,S(S(0))))$
$\rightarrow_{r2} S(S(A(0,S(0))))$	$\rightarrow_{r1} A(0,S(S(S(0))))$
$\rightarrow_{r1} S(S(S(S(0))))$	$\rightarrow_{r1} S(S(S(S(0))))$

결과는 4 ( $S(S(S(S(0))))$ )이다.

$\operatorname{A}(m, n)$ 을 계산하기 위해 스택을 사용할 수도 있다. 처음에는 스택에 $\langle m,n \rangle$ 만 넣고, 스택의 길이가 1이 될 때까지 다음 규칙에 따라 스택의 상위 두 요소를 반복적으로 대체한다.^[5]

: $\begin{array}{lllllllll}\text{(r1)} & 0 &,& n & \rightarrow & (n+1) \\\text{(r2)} & (m+1) &,& 0 & \rightarrow & m &,& 1 \\\text{(r3)} & (m+1) &,& (n+1) & \rightarrow & m &,& (m+1) &,& n\end{array}$

스택 기반 계산 과정은 다음과 같다.

'''WHILE''' 스택 길이 > 1

{

'''POP''' 스택 상위 2개 요소 $x, y$ (y가 가장 위);

'''IF''' $x = 0$ '''THEN PUSH''' $(y+1)$ (규칙 r1)

'''ELSE IF''' $y = 0$ '''THEN PUSH''' $(x-1)$ , $1$ (규칙 r2)

'''ELSE PUSH''' $(x-1)$ , $x$ , $(y-1)$ (규칙 r3)

}

'''예시: 입력 $\langle 2,1 \rangle$ (즉, $A(2,1)$ )에 대한 스택 계산'''

스택 상태	적용 규칙	해당 축약^[6]
$\langle 2,1 \rangle$	-	$A(2,1)$
$\langle 1, 2, 0 \rangle$	r3	$A(1,A(2,0))$
$\langle 1, 1, 1 \rangle$	r2 (A(2,0) → A(1,1))	$A(1,A(1,1))$
$\langle 1, 0, 1, 0 \rangle$	r3 (A(1,1) → A(0,A(1,0)))	$A(1,A(0,A(1,0)))$
$\langle 1, 0, 0, 1 \rangle$	r2 (A(1,0) → A(0,1))	$A(1,A(0,A(0,1)))$
$\langle 1, 0, 2 \rangle$	r1 (A(0,1) → 2)	$A(1,A(0,2))$
$\langle 1, 3 \rangle$	r1 (A(0,2) → 3)	$A(1,3)$
$\langle 0, 1, 2 \rangle$	r3	$A(0,A(1,2))$
$\langle 0, 0, 1, 1 \rangle$	r3 (A(1,2) → A(0,A(1,1)))	$A(0,A(0,A(1,1)))$
$\langle 0, 0, 0, 1, 0 \rangle$	r3 (A(1,1) → A(0,A(1,0)))	$A(0,A(0,A(0,A(1,0))))$
$\langle 0, 0, 0, 0, 1 \rangle$	r2 (A(1,0) → A(0,1))	$A(0,A(0,A(0,A(0,1))))$
$\langle 0, 0, 0, 2 \rangle$	r1 (A(0,1) → 2)	$A(0,A(0,A(0,2)))$
$\langle 0, 0, 3 \rangle$	r1 (A(0,2) → 3)	$A(0,A(0,3))$
$\langle 0, 4 \rangle$	r1 (A(0,3) → 4)	$A(0,4)$
$\langle 5 \rangle$	r1 (A(0,4) → 5)	$5$

최종 결과는 5이다.

모든 $m,n$ 에 대해 $A(m,n)$ 의 계산은 $(A(m,n) + 1)^m$ 단계 이하가 소요된다.
$\operatorname{A}(m,n)$ 의 계산에서 스택의 최대 길이는 $m>0$ 일 때 $\operatorname{A}(m,n)$ 이다.
Grossman과 Zeitman(1988)은 $\mathcal{O}(m \operatorname{A}(m,n))$ 시간과 $\mathcal{O}(m)$ 공간 내에서 $\operatorname{A}(m,n)$ 을 계산하는 반복적 알고리즘을 제시했다.

=== 반복 1변수 아커만 함수 ===

반복 1변수 아커만 함수

\operatorname{A}_{m}(n) = \operatorname{A}(m,n)

의 정의는 다음과 같은 축약 규칙을 도출한다.

:

\begin{array}{lll}\text{(r4)} & A(S(0),0,n)    & \rightarrow & S(n) \\\text{(r5)} & A(S(0),S(m),n) & \rightarrow & A(S(n),m,S(0)) \\\text{(r6)} & A(S(S(x)),m,n) & \rightarrow & A(S(0),m,A(S(x),m,n))\end{array}

여기서

A(k, m, n)

는

k

번째 반복,

m

은 함수 인덱스,

n

은 입력값을 나타낸다고 해석할 수 있다. 함수 합성은 결합 법칙이 성립하므로, 규칙 r6 대신 다음과 같이 정의할 수도 있다.

:

\begin{array}{lll}\text{(r7)} & A(S(S(x)),m,n) & \rightarrow & A(S(x),m,A(S(0),m,n))\end{array}

스택을 사용하여 계산할 수 있다. 처음 스택에는 세 개의 요소

\langle 1,m,n \rangle

을 넣고, 스택 길이가 1이 될 때까지 다음 규칙에 따라 스택의 상위 세 요소를 반복적으로 대체한다.^[5]

:

\begin{array}{lllllllll}\text{(r4)} & 1   &, 0   &, n & \rightarrow & (n+1) \\\text{(r5)} & 1   &, (m+1) &, n & \rightarrow & (n+1) &, m &, 1 \\\text{(r6)} & (x+2) &, m   &, n & \rightarrow & 1 &, m &, (x+1) &, m &, n \\\end{array}

규칙 r7을 사용하는 경우, r6 규칙은 다음과 같이 바뀐다.

:

\begin{array}{lllllllll}\text{(r7)} & (x+2) &, m   &, n & \rightarrow & (x+1) &, m &, 1 &, m &, n\end{array}

'''예시: 입력

\langle 1,2,1 \rangle

(즉,

A_2(1)

) 계산'''

규칙 r6 사용 시 스택 구성:

:

\begin{align}    & \langle 1,2,1 \rangle    \rightarrow_{r5} \langle 2,1,1 \rangle    \rightarrow_{r6} \langle 1,1,1,1,1 \rangle    \rightarrow_{r5} \langle 1,1,2,0,1 \rangle    \rightarrow_{r6} \langle 1,1,1,0,1,0,1 \rangle \\    & \rightarrow_{r4} \langle 1,1,1,0,2 \rangle    \rightarrow_{r4} \langle 1,1,3 \rangle    \rightarrow_{r5} \langle 4,0,1 \rangle    \rightarrow_{r6} \langle 1,0,3,0,1 \rangle    \rightarrow_{r6} \langle 1,0,1,0,2,0,1 \rangle \\    & \rightarrow_{r6} \langle 1,0,1,0,1,0,1,0,1 \rangle    \rightarrow_{r4} \langle 1,0,1,0,1,0,2 \rangle    \rightarrow_{r4} \langle 1,0,1,0,3 \rangle    \rightarrow_{r4} \langle 1,0,4 \rangle    \rightarrow_{r4} \langle 5 \rangle    \end{align}

규칙 r7 사용 시 스택 구성:

:

\begin{align}    & \langle 1,2,1 \rangle    \rightarrow_{r5} \langle 2,1,1 \rangle    \rightarrow_{r7} \langle 1,1,1,1,1 \rangle    \rightarrow_{r5} \langle 1,1,2,0,1 \rangle    \rightarrow_{r7} \langle 1,1,1,0,1,0,1 \rangle \\    & \rightarrow_{r4} \langle 1,1,1,0,2 \rangle    \rightarrow_{r4} \langle 1,1,3 \rangle    \rightarrow_{r5} \langle 4,0,1 \rangle    \rightarrow_{r7} \langle 3,0,1,0,1 \rangle    \rightarrow_{r4} \langle 3,0,2 \rangle \\    & \rightarrow_{r7} \langle 2,0,1,0,2 \rangle    \rightarrow_{r4} \langle 2,0,3 \rangle    \rightarrow_{r7} \langle 1,0,1,0,3 \rangle    \rightarrow_{r4} \langle 1,0,4 \rangle    \rightarrow_{r4} \langle 5 \rangle    \end{align}

주어진 입력에 대해 2항 TRS와 1항 TRS는 동일한 단계 수로 수렴하며, 동일한 축약 규칙을 사용한다 (r1, r2, r3은 각각 r4, r5, r6/r7과 대응). 예를 들어, $A(2,1)$ 과 $A_2(1)$ 의 계산 모두 14단계로 수렴한다. 차이는 축약 규칙이 적용되는 순서이다.
규칙 {r4, r5, r6}을 사용할 때 스택의 최대 길이는 $2 \times A(m,n)$ 미만이다. 규칙 r7을 사용하면 스택 최대 길이는 $2(m+2)$ 로 제한된다. 스택 길이는 재귀 깊이를 반영하므로, 규칙 r7을 사용하는 것이 최대 재귀 깊이 측면에서 더 효율적일 수 있다.^[7]

=== 하이퍼 연산 기반 ===

아커만 함수는 하이퍼연산 시퀀스로도 표현될 수 있다.

:

A(m,n) = \begin{cases}n+1 & m=0 \\2[m](n+3) - 3 & m>0 \\\end{cases}

여기서

a[m]b

는 하이퍼 연산을 나타낸다. 이는 Buck의 함수

\operatorname{F}(m,n) = 2[m]n

를 사용하여 다음과 같이 표현할 수도 있다.

:

A(m,n) = \begin{cases}n+1 & m=0 \\F(m,n+3) - 3 & m>0 \\\end{cases}

Buck의 함수

\operatorname{F}(m,n)

자체도 아커만 함수의 변형이며, 다음과 같은 축약 규칙으로 계산할 수 있다. (여기서

F(k, m, n)

는

k

번째 반복,

m

은 하이퍼 연산 레벨,

n

은 입력값을 나타낸다고 해석 가능)

:

\begin{array}{lll}\text{(b1)} & F(S(0),0,n)          & \rightarrow & S(n) \\\text{(b2)} & F(S(0),S(0),0)       & \rightarrow & S(S(0)) \\\text{(b3)} & F(S(0),S(S(0)),0)    & \rightarrow & 0 \\\text{(b4)} & F(S(0),S(S(S(m))),0) & \rightarrow & S(0) \\\text{(b5)} & F(S(0),S(m),S(n))    & \rightarrow & F(S(n),m,F(S(0),S(m),0)) \\\text{(b6)} & F(S(S(x)),m,n)       & \rightarrow & F(S(0),m,F(S(x),m,n))\end{array}

규칙 b6 대신 다음 규칙을 사용할 수도 있다.

:

\begin{array}{lll}\text{(b7)} & F(S(S(x)),m,n)       & \rightarrow & F(S(x),m,F(S(0),m,n))\end{array}

아커만 함수

A(m,n)

를 계산하기 위해 다음 세 가지 축약 규칙을 추가한다.

:

\begin{array}{lll}\text{(r8)}  & A(0,n)	     & \rightarrow & S(n) \\\text{(r9)}  & A(S(m),n)     & \rightarrow & P(F(S(0),S(m),S(S(S(n))))) \\\text{(r10)} & P(S(S(S(m)))) & \rightarrow & m \\\end{array}

여기서

P(x)

는

x-3

을 계산하는 연산자이다. 즉,

A(m,n) = F(m, n+3) - 3

관계를 TRS로 표현한 것이다.

'''예시:

A(2,1) \rightarrow_{*} 5

계산'''

A(2,1)

계산은 규칙 r9에 의해

P(F(1, 2, 4))

로 변환된다. 이제

F(1, 2, 4)

를 계산한다. (이는 Buck 함수로는

F(2,4)

에 해당)

규칙 b7 사용 시 축약 과정:^[6]

\begin{align}    F(1, 2, 4) & \rightarrow_{b5} F(4, 1, F(1, 2, 0)) \\    & \rightarrow_{b3} F(4, 1, 0) \\    & \rightarrow_{b7} F(3, 1, F(1, 1, 0)) \\    & \rightarrow_{b2} F(3, 1, 2) \\    & \rightarrow_{b7} F(2, 1, F(1, 1, 2)) \\    & \rightarrow_{b5} F(2, 1, F(2, 0, F(1, 1, 0))) \\    & \rightarrow_{b2} F(2, 1, F(2, 0, 2)) \\    & \rightarrow_{b7} F(2, 1, F(1, 0, F(1, 0, 2))) \\    & \rightarrow_{b1} F(2, 1, F(1, 0, 3)) \\    & \rightarrow_{b1} F(2, 1, 4) \\    & \rightarrow_{b7} F(1, 1, F(1, 1, 4)) \\    & \rightarrow_{b5} F(1, 1, F(4, 0, F(1, 1, 0))) \\    & \rightarrow_{b2} F(1, 1, F(4, 0, 2)) \\    & \rightarrow_{b7} F(1, 1, F(3, 0, F(1, 0, 2))) \\    & \rightarrow_{b1} F(1, 1, F(3, 0, 3)) \\    & \rightarrow_{b7} F(1, 1, F(2, 0, F(1, 0, 3))) \\    & \rightarrow_{b1} F(1, 1, F(2, 0, 4)) \\    & \rightarrow_{b7} F(1, 1, F(1, 0, F(1, 0, 4))) \\    & \rightarrow_{b1} F(1, 1, F(1, 0, 5)) \\    & \rightarrow_{b1} F(1, 1, 6) \\    & \rightarrow_{b5} F(6, 0, F(1, 1, 0)) \\    & \rightarrow_{b2} F(6, 0, 2) \\    & \rightarrow_{b7} F(5, 0, F(1, 0, 2)) \\    & \rightarrow_{b1} F(5, 0, 3) \\    & \rightarrow_{b7} F(4, 0, F(1, 0, 3)) \\    & \rightarrow_{b1} F(4, 0, 4) \\    & \rightarrow_{b7} F(3, 0, F(1, 0, 4)) \\    & \rightarrow_{b1} F(3, 0, 5) \\    & \rightarrow_{b7} F(2, 0, F(1, 0, 5)) \\    & \rightarrow_{b1} F(2, 0, 6) \\    & \rightarrow_{b7} F(1, 0, F(1, 0, 6)) \\    & \rightarrow_{b1} F(1, 0, 7) \\    & \rightarrow_{b1} 8    \end{align}

규칙 b6 사용 시 축약 과정:^[6]

\begin{align}    F(1, 2, 4) & \rightarrow_{b5} F(4, 1, F(1, 2, 0)) \\    & \rightarrow_{b3} F(4, 1, 0) \\    & \rightarrow_{b6} F(1, 1, F(3, 1, 0)) \\    & \rightarrow_{b6} F(1, 1, F(1, 1, F(2, 1, 0))) \\    & \rightarrow_{b6} F(1, 1, F(1, 1, F(1, 1, F(1, 1, 0)))) \\    & \rightarrow_{b2} F(1, 1, F(1, 1, F(1, 1, 2))) \\    & \rightarrow_{b5} F(1, 1, F(1, 1, F(2, 0, F(1, 1, 0)))) \\    & \rightarrow_{b2} F(1, 1, F(1, 1, F(2, 0, 2))) \\    & \rightarrow_{b6} F(1, 1, F(1, 1, F(1, 0, F(1, 0, 2)))) \\    & \rightarrow_{b1} F(1, 1, F(1, 1, F(1, 0, 3))) \\    & \rightarrow_{b1} F(1, 1, F(1, 1, 4)) \\    & \rightarrow_{b5} F(1, 1, F(4, 0, F(1, 1, 0))) \\    & \rightarrow_{b2} F(1, 1, F(4, 0, 2)) \\    & \rightarrow_{b6} F(1, 1, F(1, 0, F(3, 0, 2))) \\    & \rightarrow_{b6} F(1, 1, F(1, 0, F(1, 0, F(2, 0, 2)))) \\    & \rightarrow_{b6} F(1, 1, F(1, 0, F(1, 0, F(1, 0, F(1, 0, 2))))) \\    & \rightarrow_{b1} F(1, 1, F(1, 0, F(1, 0, F(1, 0, 3)))) \\    & \rightarrow_{b1} F(1, 1, F(1, 0, F(1, 0, 4))) \\    & \rightarrow_{b1} F(1, 1, F(1, 0, 5)) \\    & \rightarrow_{b1} F(1, 1, 6) \\    & \rightarrow_{b1} F(1, 0, 7) \\    & \rightarrow_{b1} 8    \end{align}

두 경우 모두

F(1, 2, 4)

는 8로 계산된다. 마지막으로 규칙 r10을 적용하여

P(8) \rightarrow_{r10} 5

를 얻는다. 따라서

A(2,1) = 5

이다.

규칙 b6을 사용하면 깊은 재귀 호출( $F(F(...))$ )이 발생하여 최대 재귀 깊이가 $A(m,n)+1$ 에 달할 수 있다.
규칙 b7을 사용하면 반복 루프와 유사하게 작동하여^[8] 최대 재귀 깊이가 $(m+1)$ 로 제한되어 더 효율적이다.
두 방식 모두 동일한 수의 축약 단계를 거치며 (b6과 b7을 동일하게 간주할 때), $A(2,1)$ 계산은 총 35단계 (규칙별 횟수: b1:12, b2:4, b3:1, b5:4, b6/b7:12, r9:1, r10:1)가 소요된다. 적용 순서만 다르다.
실제 실행 시간을 줄이기 위해 메모이제이션 기법을 사용하여 하위 결과 재계산을 피할 수 있다.

9. Properties

$= 2 \uparrow\uparrow 65536 - 3$ $A(4, A(5, 1))$ $A(4, A(5, 2))$ $A(4, A(5, 3))$ $2 \uparrow\uparrow\uparrow (n+3) - 3$ 6 $A(5, 1)$ $A(5, A(6, 0))$ $A(5, A(6, 1))$ $A(5, A(6, 2))$ $A(5, A(6, 3))$ $2 \uparrow\uparrow\uparrow\uparrow (n+3) - 3$

아커만 함수

1. 개요

더 읽어볼만한 페이지

2. 역사

3. 정의와 특성

4. 값들의 표

5. 아커만 함수가 원시 재귀 함수가 아니라는 증명

6. 역함수

7. 벤치마크로 사용

8. 계산

9. Properties

참조